package thinker;

import chess.*;

public class AlphaBetaSearch {
	public static byte WIN = 1;
	public static byte FORBIDDEN = 0;
	public static int MAX_DEPTH = 2;
	public static final int ADJ1 = 8;
	public static final int ADJ2 = 24;
	public static final byte[] adjR = { -1, -1, -1, 0, 0, 1, 1, 1, -2, -2, -2,
			-2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 2, 2, 2 };
	public static final byte[] adjC = { -1, 0, 1, -1, 1, -1, 0, 1, -2, -1, 0,
			1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2 };

	private Node startNode;
	private Evaluator eval;
	private Chess[] nc = new Chess[225];
	private int[] nv = new int[225];

	public AlphaBetaSearch(ChessBoard b) {
		startNode = new Node(b);
		eval = new Evaluator();
		Node.count = 0;
	}

	private boolean reachTermCond(Node n) {
		// TODO Check the time, space, search depth limit
		if (n.depth >= MAX_DEPTH) {
			return true;
		}
		return false;
	}

	public static byte isForbiddenOrWon(Node n) {
		ChessBoard b = n.getBoard();
		if (n.depth < 1)
			return -1;
		if (n.lastMove.color == ChessBoard.BLACK) // judge forbidden
		{
			return checkForbiddenOrWon(n.getBoard(), n.lastMove.row,
					n.lastMove.col);
		}
		else {
			int i = n.lastMove.row;
			int value = 0;
			while (b.isBlack(i++, n.lastMove.col) && i < 15)
				// check if the number if
				value++;
			i = Math.max(n.lastMove.row - 1, 0);
			while (b.isBlack(i--, n.lastMove.col) && i >= 0)
				value++;
			if (value >= 5)
				return WIN;

			value = 0;
			i = n.lastMove.col;
			while (b.isBlack(n.lastMove.row, i++) && i < 15)
				// check if the number if
				value++;
			i = Math.max(n.lastMove.col - 1, 0);
			while (b.isBlack(n.lastMove.row, i--) && i >= 0)
				value++;
			if (value >= 5)
				return WIN;

			value = 0;
			i = n.lastMove.col;
			int j = n.lastMove.row;
			while (b.isBlack(j++, i++) && i < 15 && j < 15)
				// check if the number is
				value++;
			i = Math.max(n.lastMove.col - 1, 0);
			j = Math.max(n.lastMove.row - 1, 0);
			while (b.isBlack(j--, i--) && i >= 0 && j >= 0)
				value++;
			if (value >= 5)
				return WIN;

			value = 0;
			i = n.lastMove.col;
			j = n.lastMove.row;
			while (b.isBlack(j--, i++) && i < 15 && j >= 0)
				// check if the number is
				value++;
			i = Math.max(n.lastMove.col - 1, 0);
			j = Math.min(n.lastMove.row + 1, 14);
			while (b.isBlack(j++, i--) && i >= 0 && j < 15)
				value++;
			if (value >= 5)
				return WIN;
			return -1;
		}

	}

	public static byte checkForbiddenOrWon(ChessBoard b, byte row, byte col) {
		b = new ChessBoard(b);
		byte[] linkedNumber = new byte[8];
		byte[] emptyNumber = new byte[8];
		byte[] jumpLinkedNumber = new byte[8];
		byte[] jumpEmptyNumber = new byte[8];
		byte[] doubleJumpLinkedNumber = new byte[8];
		b.update(new Chess(ChessBoard.BLACK, row, col));
		for (int i = 0; i < 8; i++) {
			linkedNumber[i] = emptyNumber[i] = jumpLinkedNumber[i] = jumpEmptyNumber[i] = doubleJumpLinkedNumber[i] = 0;
		}
		int i, j;
		for (i = row - 1; i >= 0 && b.isBlack(i, col); i--, linkedNumber[0]++)
			;
		for (; i >= 0 && (b.isNone(i, col) || b.isMark(i, col)); i--, emptyNumber[0]++)
			;
		for (; i >= 0 && b.isBlack(i, col); i--, jumpLinkedNumber[0]++)
			;
		for (; i >= 0 && (b.isNone(i, col) || b.isMark(i, col)); i--, jumpEmptyNumber[0]++)
			;
		for (; i >= 0 && b.isBlack(i, col); i--, doubleJumpLinkedNumber[0]++)
			;

		for (i = row - 1, j = col - 1; i >= 0 && j >= 0 && b.isBlack(i, j); i--, j--, linkedNumber[1]++)
			;
		for (; i >= 0 && j >= 0 && (b.isNone(i, j) && b.isNone(i, j)); i--, j--, emptyNumber[1]++)
			;
		for (; i >= 0 && j >= 0 && (b.isBlack(i, j)); i--, j--, jumpLinkedNumber[1]++)
			;
		for (; i >= 0 && j >= 0 && (b.isNone(i, j) && b.isNone(i, j)); i--, j--, jumpEmptyNumber[1]++)
			;
		for (; i >= 0 && j >= 0 && (b.isBlack(i, j)); i--, j--, doubleJumpLinkedNumber[1]++)
			;

		for (j = col - 1; j >= 0 && b.isBlack(row, j); j--, linkedNumber[2]++)
			;
		for (; j >= 0 && (b.isNone(row, j) || b.isMark(row, j)); j--, emptyNumber[2]++)
			;
		for (; j >= 0 && b.isBlack(row, j); j--, jumpLinkedNumber[2]++)
			;
		for (; j >= 0 && (b.isNone(row, j) || b.isMark(row, j)); j--, jumpEmptyNumber[2]++)
			;
		for (; j >= 0 && b.isBlack(row, j); j--, doubleJumpLinkedNumber[2]++)
			;

		for (i = row + 1, j = col - 1; i < 15 && j >= 0 && b.isBlack(i, j); i++, j--, linkedNumber[3]++)
			;
		for (; i < 15 && j >= 0 && (b.isNone(i, j) && b.isNone(i, j)); i++, j--, emptyNumber[3]++)
			;
		for (; i < 15 && j >= 0 && (b.isBlack(i, j)); i++, j--, jumpLinkedNumber[3]++)
			;
		for (; i < 15 && j >= 0 && (b.isNone(i, j) && b.isNone(i, j)); i++, j--, jumpEmptyNumber[3]++)
			;
		for (; i < 15 && j >= 0 && (b.isBlack(i, j)); i++, j--, doubleJumpLinkedNumber[3]++)
			;

		for (i = row + 1; i < 15 && b.isBlack(i, col); i++, linkedNumber[4]++)
			;
		for (; i < 15 && (b.isNone(i, col) || b.isMark(i, col)); i++, emptyNumber[4]++)
			;
		for (; i < 15 && b.isBlack(i, col); i++, jumpLinkedNumber[4]++)
			;
		for (; i < 15 && (b.isNone(i, col) || b.isMark(i, col)); i++, jumpEmptyNumber[4]++)
			;
		for (; i < 15 && b.isBlack(i, col); i++, doubleJumpLinkedNumber[4]++)
			;

		for (i = row + 1, j = col + 1; i < 15 && j < 15 && b.isBlack(i, j); i++, j++, linkedNumber[5]++)
			;
		for (; i < 15 && j < 15 && (b.isNone(i, j) && b.isNone(i, j)); i++, j++, emptyNumber[5]++)
			;
		for (; i < 15 && j < 15 && (b.isBlack(i, j)); i++, j++, jumpLinkedNumber[5]++)
			;
		for (; i < 15 && j < 15 && (b.isNone(i, j) && b.isNone(i, j)); i++, j++, jumpEmptyNumber[5]++)
			;
		for (; i < 15 && j < 15 && (b.isBlack(i, j)); i++, j++, doubleJumpLinkedNumber[5]++)
			;

		for (j = col + 1; j < 15 && b.isBlack(row, j); j++, linkedNumber[6]++)
			;
		for (; j < 15 && (b.isNone(row, j) || b.isMark(row, j)); j++, emptyNumber[6]++)
			;
		for (; j < 15 && b.isBlack(row, j); j++, jumpLinkedNumber[6]++)
			;
		for (; j < 15 && (b.isNone(row, j) || b.isMark(row, j)); j++, jumpEmptyNumber[6]++)
			;
		for (; j < 15 && b.isBlack(row, j); j++, doubleJumpLinkedNumber[6]++)
			;

		for (i = row - 1, j = col + 1; i >= 0 && j < 15 && b.isBlack(i, j); i--, j++, linkedNumber[7]++)
			;
		for (; i >= 0 && j < 15 && (b.isNone(i, j) && b.isNone(i, j)); i--, j++, emptyNumber[7]++)
			;
		for (; i >= 0 && j < 15 && (b.isBlack(i, j)); i--, j++, jumpLinkedNumber[7]++)
			;
		for (; i >= 0 && j < 15 && (b.isNone(i, j) && b.isNone(i, j)); i--, j++, jumpEmptyNumber[7]++)
			;
		for (; i >= 0 && j < 15 && (b.isBlack(i, j)); i--, j++, doubleJumpLinkedNumber[7]++)
			;

		for (i = 0; i < 4; i++) {
			if (linkedNumber[i] + linkedNumber[i + 4] == 4)
				return WIN;
		}
		b.update(new Chess(ChessBoard.NONE, row, col));
		int Four = 0;
		int Three = 0;
		for (i = 0; i < 4; i++) {
			if (linkedNumber[i] + linkedNumber[i + 4] > 4)
				return FORBIDDEN;
			else if (linkedNumber[i] + linkedNumber[i + 4] == 3) {
				boolean isFour = false;
				if (emptyNumber[i] > 0) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						isFour = true;
				}
				if (emptyNumber[i + 4] > 0) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						isFour = true;
				}
				if (isFour)
					Four++;
			}
			else if (linkedNumber[i] + linkedNumber[i + 4] == 2) {
				if (emptyNumber[i] == 1 && jumpLinkedNumber[i] == 1) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						Four++;
				}
				if (emptyNumber[i + 4] == 1 && jumpLinkedNumber[i + 4] == 1) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						Four++;
				}
				boolean isThree = false;
				if ((emptyNumber[i] > 2 || emptyNumber[i] == 2
						&& jumpLinkedNumber[i] == 0)
						&& (emptyNumber[i + 4] > 1 || emptyNumber[i + 4] == 1
								&& jumpLinkedNumber[i + 4] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						isThree = true;
				}
				if ((emptyNumber[i + 4] > 2 || emptyNumber[i + 4] == 2
						&& jumpLinkedNumber[i + 4] == 0)
						&& (emptyNumber[i] > 1 || emptyNumber[i] == 1
								&& jumpLinkedNumber[i] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						isThree = true;
				}
				if (isThree)
					Three++;
			}
			else if (linkedNumber[i] + linkedNumber[i + 4] == 1) {
				if (emptyNumber[i] == 1 && jumpLinkedNumber[i] == 2) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						Four++;
				}
				if (emptyNumber[i + 4] == 1 && jumpLinkedNumber[i + 4] == 2) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						Four++;
				}

				if (emptyNumber[i] == 1
						&& jumpLinkedNumber[i] == 1
						&& (jumpEmptyNumber[i] > 1 || jumpEmptyNumber[i] == 1
								&& doubleJumpLinkedNumber[i] == 0)
						&& (emptyNumber[i + 4] > 1 || emptyNumber[i + 4] == 1
								&& jumpLinkedNumber[i + 4] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						Three++;
				}
				if (emptyNumber[i + 4] == 1
						&& jumpLinkedNumber[i + 4] == 1
						&& (jumpEmptyNumber[i + 4] > 1 || jumpEmptyNumber[i + 4] == 1
								&& doubleJumpLinkedNumber[i + 4] == 0)
						&& (emptyNumber[i] > 1 || emptyNumber[i] == 1
								&& jumpLinkedNumber[i] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						Three++;
				}
			}
			else if (linkedNumber[i] + linkedNumber[i + 4] == 0) {
				if (emptyNumber[i] == 1 && jumpLinkedNumber[i] == 3) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						Four++;
				}
				if (emptyNumber[i + 4] == 1 && jumpLinkedNumber[i + 4] == 3) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						Four++;
				}
				if (emptyNumber[i] == 1
						&& jumpLinkedNumber[i] == 2
						&& (jumpEmptyNumber[i] > 1 || jumpEmptyNumber[i] == 1
								&& doubleJumpLinkedNumber[i] == 0)
						&& (emptyNumber[i + 4] > 1 || emptyNumber[i + 4] == 1
								&& jumpLinkedNumber[i + 4] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i], i) != true)
						Three++;
				}
				if (emptyNumber[i + 4] == 1
						&& jumpLinkedNumber[i + 4] == 2
						&& (jumpEmptyNumber[i + 4] > 1 || jumpEmptyNumber[i + 4] == 1
								&& doubleJumpLinkedNumber[i + 4] == 0)
						&& (emptyNumber[i] > 1 || emptyNumber[i] == 1
								&& jumpLinkedNumber[i] == 0)) {
					if (isKeyPiontForbidden(b, row, col, linkedNumber[i + 4],
							i + 4) != true)
						Three++;
				}
			}
		}
		if (Three > 1 || Four > 1)
			return FORBIDDEN;
		return -1;

	}

	private static boolean isKeyPiontForbidden(ChessBoard b, int row, int col,
			int link, int i) {
		int tempRow = 0, tempCol = 0;
		link++;
		if (i >= 4)
			link = -link;
		switch (i % 4) {
		case 0:
			tempRow = row - link;
			tempCol = col;
			break;
		case 1:
			tempRow = row - link;
			tempCol = col - link;
			break;
		case 2:
			tempRow = row;
			tempCol = col - link;
			break;
		case 3:
			tempRow = row + link;
			tempCol = col - link;
			break;
		}
		b.update(new Chess(ChessBoard.BLACK, (byte) row, (byte) col));
		b.update(new Chess(ChessBoard.BLACK, (byte) tempRow, (byte) tempCol));
		byte result = checkForbiddenOrWon(b, (byte) tempRow, (byte) tempCol);
		b.update(new Chess(ChessBoard.NONE, (byte) row, (byte) col));
		b.update(new Chess(ChessBoard.NONE, (byte) tempRow, (byte) tempCol));
		if (result == FORBIDDEN)
			return true;
		return false;
	}

	private boolean isOnBoard(int r, int c) {
		return (r >= 0 && r < ChessBoard.ROWS && c >= 0 && c < ChessBoard.COLS);
	}

	private int getStaticWorth(Node n) {
		ChessBoard b = n.getBoard();
		return eval.calStaticValue(b);
	}

	private void expand(Node n) {
		ChessBoard b;
		Chess ch, ncc;
		int nvv;
		byte r, c;
		int s;

		s = 0;
		b = n.getBoard();
		for (int i = 0; i < b.chessed; i++) {
			ch = b.chessList[b.chessed - 1 - i];
			for (int k = 0; k < ADJ1; k++) {
				r = (byte) (ch.row + adjR[k]);
				c = (byte) (ch.col + adjC[k]);
				if (isOnBoard(r, c))
					if (b.isNone(r, c)) {
						b.board[r][c] = ChessBoard.MARK;
						nc[s] = new Chess(b.turn, r, c);
//						nv[s] = eval.newChessValue(b, nc[s]);
						s++;
//						if (s>150) b.print();
					}
			}
		}
		if (n.depth < 2)
			for (int i = 0; i < b.chessed; i++) {
				ch = b.chessList[b.chessed - i - 1];
				for (int k = ADJ1; k < ADJ2; k++) {
					r = (byte) (ch.row + adjR[k]);
					c = (byte) (ch.col + adjC[k]);
					if (isOnBoard(r, c))
						if (b.isNone(r, c)) {
							b.board[r][c] = ChessBoard.MARK;
							nc[s] = new Chess(b.turn, r, c);
//							nv[s] = eval.newChessValue(b, nc[s]);
							s++;
//							if (s>150) b.print();
						}
				}
			}

//		for (int i = 0; i < s - 1; i++)
//			for (int j = i + 1; j < s; j++)
//				if (true && (n.turn == Node.myColor && nv[i] < nv[j])
//						|| (n.turn != Node.myColor && nv[i] > nv[j])) {
//					nvv = nv[i];
//					nv[i] = nv[j];
//					nv[j] = nvv;
//					ncc = nc[i];
//					nc[i] = nc[j];
//					nc[j] = ncc;
//				}
		for (int i = 0; i < s; i++)
			n.addChild(nc[i]);

		System.out.println(Node.count);
	}

	private int abWorth(Node n, int alpha, int beta) {
		int w;
		if (reachTermCond(n)) {
			w = getStaticWorth(n);
			n.worth = w;
			return w;
		}
		byte value = isForbiddenOrWon(n);
		if (value == FORBIDDEN) {
			w = (n.turn != Node.myColor ? Node.MIN : Node.MAX);
			n.worth = w;
			return w;
		}
		else if ((w = eval.isSuccessed(n.getBoard())) != 0) {
			n.worth = w;
			return w;
		}
		expand(n);
		Node node = n.children;
		if (n.isMaxNode()) {
			while (node != null) {
				alpha = Math.max(alpha, abWorth(node, alpha, beta));
				if (alpha >= beta) {
					n.worth = alpha;
					return beta;
				}
				node = node.nextNode;
			}
			n.worth = alpha;
			return alpha;
		}
		else if (n.isMinNode()) {
			while (node != null) {
				beta = Math.min(beta, abWorth(node, alpha, beta));
				if (beta <= alpha) {
					n.worth = beta;
					return alpha;
				}
				node = node.nextNode;
			}
			n.worth = beta;
			return beta;
		}
		return 0;
	}

	public Chess bestFirstMove() {
		abWorth(startNode, Node.MIN, Node.MAX);
		Chess c = null;
		int w = Node.MIN;
		Node n = startNode.children;
		while (n != null) {
			if (c == null) {
				c = n.lastMove;
			}
			else if (n.worth > w) {
				w = n.worth;
				c = n.lastMove;
			}
			n = n.nextNode;
		}
		return c;
	}

}
